package com.mlamp.动态规划;

public class 两个子序列的最大点积 {

    public static void main(String[] args) {
        int[] num1 = new int[]{2, 1, -2, 5};
        int[] num2 = new int[]{3, 0, -6};
        int i = maxDotProduct(num1, num2);
        System.out.println(i);
        i = maxProduct(num1, num2);
        System.out.println(i);

        i = maxProduct(new int[]{3, -2}, new int[]{2, -6, 7});
        System.out.println(i);

        i = maxPro(new int[]{3, -2}, new int[]{2, -6, 7});
        System.out.println(i);
    }


    /**
     * 设dp[i][j] 表示num1[0...i] 与num2[0....j]的非空子序列的最大点积。
     * dp方程式 dp[i][j] = max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]+ num1[i] * num2[j], num1[i] * num2[j]);
     *
     * @param num1
     * @param num2
     * @return
     */
    public static int maxProduct(int[] num1, int[] num2) {
        int len_m = num1.length, len_n = num2.length;
        int[][] f = new int[len_m][len_n];
        for (int i = 0; i < len_m; i++) {
            for (int j = 0; j < len_n; j++) {
                int resij = num1[i] * num2[j];
                f[i][j] = resij;
                if (i > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                }
                if (j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                }
                if (i > 0 && j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + resij);
                }
            }
        }
        return f[len_m - 1][len_n - 1];
    }


    public static int maxPro(int[] num1, int[] num2) {
        int m = num1.length, n = num2.length;
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int xij = num1[i] * num2[j];
                res[i][j] = xij;
                if (i > 0) {
                    res[i][j] = Math.max(res[i][j], res[i - 1][j]);
                }
                if (j > 0) {
                    res[i][j] = Math.max(res[i][j], res[i][j - 1]);
                }
                if (i > 0 && j > 0) {
                    res[i][j] = Math.max(res[i][j], res[i - 1][j - 1] + xij);
                }
            }
        }
        return res[m - 1][n - 1];
    }


    public static int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int xij = nums1[i] * nums2[j];
                f[i][j] = xij;
                if (i > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                }
                if (j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                }

                if (i > 0 && j > 0) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + xij);
                }
            }
        }
        return f[m - 1][n - 1];
    }
}
